1. Field of the Invention
The invention relates generally to the watermarking of content that is represented by digital representations and more specifically to the problem of detecting watermarks in digital representations that have been derived via lossy transformations from an original watermarked digital representation.
2. Description of Related Art
Nowadays, the easiest way to work with pictures or sounds is often to make digital representations of them. Once the digital representation is made, anyone with a computer can copy the digital representation without degradation, can manipulate it, and can send it virtually instantaneously to anywhere in the world. The Internet, finally, has made it possible for anyone to distribute any digital representation from anywhere in the world
From the point of view of the owners of the digital representations, there is one problem with all of this: pirates, too, have computers, and they can use them to copy, manipulate, and distribute digital representations as easily as the legitimate owners and users can. If the owners and users of the original digital representations are to be protected against illegal copiers or forgers of the digital representations, the digital representations themselves must be protected from pirates and forgers.
One technique that is widely used to make piracy and forgery more difficult is digital watermarking. A digital watermark is a modification of a digital representation so that it contains additional information. The modification is done in such a fashion that the additional information remains substantially invisible when an analog form of the digital representation is produced by printing or displaying the digital representation, but can be located and read by those who put the additional information into the digital representation. The additional information can be anything the maker of the watermark chooses, but when watermarks are used to make piracy or forgery more difficult, the additional information is typically ownership or copyright information about the digital representation or information that can be used to authenticate the digital representation or an analog form produced from the digital representation. For further information about watermarking, see Jian Zhao, xe2x80x9cLook, It""s Not Therexe2x80x9d, in: BYTE Magazine, January, 1997. Detailed discussions of particular techniques for digital watermarking may be found in E. Koch and J. Zhao, xe2x80x9cTowards Robust and Hidden Image Copyright Labelingxe2x80x9d, in: Proc. Of 1995 IEEE Workshop on Nonlinear Signal and Image Processing, Jun. 20-22, 1995, in U.S. Pat. No. 5,710,834, Rhoads, Method and Apparatus Responsive to a Code Signal Conveyed through a Graphic Image, issued Jan. 20, 1998, and in U.S. Pat. No. 6,359,985, Koch, et al., Technique for marking binary coded data sets, issued Mar. 19, 2002. For an example of a commercial watermarking system that uses the digital watermarking techniques disclosed in the Rhoads patent, see Digimarc Watermarking Guide, Digimarc Corporation, 1999, available at http://www.digimarc.com/support/cswater.htm in August, 2002. For an example of how digital watermarking may be used to authenticate analog forms, see U.S. Pat. No. 6,243,480, Jian Zhao, et al., Digital authentication with analog documents, issued Jun. 5, 2001.
A technical challenge in the implementation of digital watermarks is making them robust. A digital watermark is robust if it still can be detected when the content of the digital watermark has been altered, either by someone with malicious intent, or simply because the content has undergone a lossy transformation, that is, a transformation in which information is lost. Examples of transformations which may be lossy are a transformation from one kind of digital representation of the content to another kind of digital representation or compression of the digital representation of the content. The production of an analog form from the digital representation is always lossy, and physical wear of the analog form may cause further loss of information. When an analog form is scanned to produce a new digital representation, that transformation, too, is always lossy. Because of the inherent lossiness involved in producing and scanning analog forms and because analog forms are subject to physical wear, the robustness of a watermark is particularly important when it is used in the manner described in U.S. Pat. No. 6,243,480 to authenticate an analog document. It is an object of the present invention to improve the robustness of digital watermarks by improving the manner in which they are made and detected.
In one aspect, the invention concerns techniques for obtaining useful information from a watermark even where the watermark""s content is unreadable. The kinds of information obtainable include whether the watermark is present at all and whether the watermark""s content belongs to one of a small set of possibilities. These techniques all involve a particular digital representation that is supposed to have been derived from a watermarked original. The watermark in the original is made from a first watermark vector that in turn was produced using a message. When the particular digital representation is being examined, a second watermark vector is extracted from a portion of the particular digital representation which corresponds to the portion of the original in which the watermark is embedded and a third watermark vector is obtained, generally by obtaining the message and recomputing the watermark vector from the message. The third watermark vector and the second watermark vector are compared, and the degree of similarity of the second and third watermark vectors determines whether the particular digital representation contains the watermark at all and also the degree of relationship between the watermark in the particular digital representation and the watermark in the original. In one particularly useful variant, the message used to recompute the watermark vector is obtained from an analog document that is also the source of the particular digital representation.
In another aspect, the invention concerns techniques for increasing the robustness of watermarks that are used to authenticate the digital representations that contain them. In these techniques, a message is not used to produce the watermark""s content, but instead to determine the watermark""s location in the digital representation. The content need only indicate the presence of the watermark, and may thus consist of the value of a single bit. To determine whether a particular digital representation that is supposedly derived from an original that contains the watermark is authentic, the message is obtained and the locations which should contain the watermark in the particular digital representation are determined. The values at those locations are compared with the expected values for the watermark, and the authenticity of the document is determined on the basis of the comparison.
In still another aspect, the invention concerns techniques for determining whether a portion of a particular digital representation has been altered. The particular digital representation is derived from a watermarked original and the locations of the watermark in the original and the watermark""s values are both known. Values from locations in the particular digital representation that correspond to locations of the watermarks in the original are compared with the values of the watermark in the original; altered portions of the particular digital representation may be determined from a less-than-expected frequency of occurrence of the values in the altered portions.
Yet another aspect of the invention concerns techniques for embedding and/or reading watermarks which take advantage of common characteristics of a class of digital representations or analog forms in which the watermarks are used. In these techniques, the digital representation containing the watermark is analyzed to determine favorable locations for the watermarks; a mask is made that specifies the favorable locations, and the mask is used in embedding and/or reading the watermarks. The mask may be static or dynamic and the analysis may be made according to the semantic importance of areas in the digital representation, according to how the digital representation is processed after the watermark is added, according to an optical characteristic of the digital representation, or according to a factor that may affect reading of the embedded watermark.
A further aspect of the invention concerns techniques for synchronizing digital representations in order to detect a watermark or for any other purpose. In the technique, a synchronization pattern of marks is added to a digital representation which has the characteristic that information external to the improved digital representation is necessary to automatically detect the marks making up the pattern. The external information may determine the locations of the marks in the digital representation. The locations may be determined relative to a feature of the digital representation. The external information that determines the locations may be a key. A location for a mark may be selected according to a characteristic of the digital representation at the location, and the content of the digital representation at the location may be modified to make detection of the mark Under normal conditions, the pattern is not perceptible to a viewer of an image made from the digital representation.
Another technique for synchronizing digital representations is used with sequences of digital representations. Here, the same predetermined portions of the content are selected as synchronization marks in each digital representation in the sequence and the value of each selected portion is changed by a predetermined amount. To detect the synchronization marks, one sums the digital representations in the sequence. The predetermined amounts may alternate between a positive and a negative amount and the locations of the synchronization marks may be determined using a key. The synchronization marks may be used to detect and reverse a transformation in the sequence of digital images.
Other objects and advantages will be apparent to those skilled in the arts to which the invention pertains upon perusal of the following Detailed Description and drawing, wherein: